设想现在对于一个学习问题，需要从一组不同的模型中进行挑选。比如多元回归模型 $h_\theta(x)=g(\theta_0+\theta_1x+\theta_2x^2+\cdots+\theta_kx^k)$，如何自动地确定 $k$ 的取值，从而在偏差和方差之间达到较好的权衡？或者对于局部加权线性回归，如何确定带宽 $\tau$ 的值，以及对于 $\ell_1$ 正则化的支持向量机，如何确定参数 $C$ 的值？
为了方便后续的讨论，统一假定有一组有限数量的模型集合 $\mathcal{M}=\{M_1,\cdots,M_d\}$。（推广到无限数量的集合也非常容易，比如对于局部加权线性模型的带宽 $\tau$，其取值范围为 $\mathbb{R}^+$，只需要将 $\tau$ 离散化，考虑有限的若干个值即可。更一般地，这里讨论的绝大多数算法，都可以看做在模型空间范围内的优化搜索问题）
本节包括以下内容：
设想有训练集 $S$。回顾经验风险最小化，一个直观的模型选择过程如下：
这个算法的表现可能会很差。考虑多元线性回归，模型的阶越高，它对训练集 $S$ 的拟合情况就越好，从而可以得到越低的训练误差。因此，上面这个方法，总是会挑选出高方差、高阶的多元模型。
下面是 hold-out 交叉验证（也称简单交叉验证）的思路：
对未用来训练数据的 $S_{cv}$ 计算的交叉验证集误差，是泛化误差的一个更好的估计量。通常，在hold-out交叉验证中会保留四分之一到三分之一的数据，30%是最常见的选择。
hold-out交叉验证还有一个可选的步骤，在上述流程完成后，可以用模型 $M_i$ 针对整个训练集 $S$ 重新训练。（通常这会训练出稍好的模型，不过也有例外，比如学习算法非常容易收到初始条件或初始数据影响的情况，这时 $M_i$ 在 $S_{train}$ 上表现良好，并不一定也会在 $S_{cv}$ 上表现良好，这种情况最好不要执行这个重新训练的过程）
hold-out交叉验证的一个劣势在于，它“浪费”了30%的数据。即便最后使用整个训练集重新训练了模型，看上去模型挑选的过程还是只针对 $0.7m$ 的训练样本，而不是所有 $m$ 个样本，因为我们的测试的模型只使用了 $0.7m$ 的数据。当数据量非常大的时候，这通常没什么问题，但数据量小的时候，可能就需要更好的策略。
k折交叉验证，每次训练时，都只保留更少的数据：
最常见的选择是令 $k=10$。由于每次训练时保留的数据量更小，而每个模型都需要训练 $k$ 次，k折交叉验证的计算开销会比hold-out交叉验证更大。
尽管 $k=10$ 是最常用的，但当数据量非常小的时候，有时也会采用 $k=m$ 来保证每次训练尽可能保留最少的数据用于验证。这种特殊情况的k折验证，也叫作留一交叉验证 leave-one-out cross validation。
最后，尽管这里介绍交叉验证用于模型选择，实际上，交叉验证也可以用来做单个模型的效果评估。
模型选择中的一个特殊应用是特征选择。设想一个监督学习问题拥有非常大数量的特征（甚至可能 $n \gg m$），但实际上能只有一小部分特征与学习任务“有关”。即便使用了最简单的线性分类器，假设函数类的VC维依然是 $O(n)$，除非训练集足够大，否则就会有潜在的过拟合风险。
在上面的设定下，可以使用一个特征选择算法来减少特征。给定 $n$ 个特征，最多有 $2^n$ 种特征组合，所以特征选择可以转换成一个 $2^n$ 种模型的模型选择问题。如果 $n$ 很大，枚举所有 $2^n$ 种模型的计算开销将会非常大。所以，通常会采用一些探索性的搜索策略，来找到一个不错的特征子集。下面这个策略，叫做前向搜索 forward search：
最外层的循环，既可以在 $\mathcal{F}={1,\cdots,n}$ 时终止，也可以中止于 $|\mathcal{F}|$ 超过某个预设的阈值。（比如，预先评估了模型最多只使用 $x$ 个特征）
上述这个算法属于模型特征选择包装 wrapper model feature selection的一个实例，因为它是一个包装在学习算法之外的步骤，通过一定策略重复调用学习算法来评估其表现。除去前项选择之外，还有一些别的搜索策略。比如后向选择 backward search：从 $\mathcal{F}=\{1,\cdots,n\}$ 开始，每次删除一个特征直到 $\mathcal{F}=\emptyset$。
特征选择包装算法通常表现不错，但是计算开销很大。完成整个搜索过程需要 $O(n^2)$ 次对学习算法的调用。
过滤特征选择 filter feature selection 则是一个计算开销小的探索性特征选择策略。这个策略的核心，是计算出某种能表示特征 $x_i$ 对于标签 $y$ 贡献的信息量的评分 $S(i)$。这样，只要再选择其中得分最大的 $k$ 个特征即可。
可以选择皮尔森相关性的绝对值，作为评分标准。但在实际中，最长使用（尤其对于离散特征）的方法叫做互信息mutual information，定义如下： $$ MI(x_i,y) = \sum_{x_i \in \{0,1\}}\sum_{y \in \{0,1\}}p(x_i,y)log\frac{p(x_i,y)}{p(x_i)p(y)} $$ （这里的等式假定 $x_i,y$ 都是二元值。更广泛地定义会根据变量的定义域来计算）概率 $p(x_i,y),p(x_i),p(y)$ 都可以通过训练集的经验分布来进行预测。
注意到，互信息也可以表示为KL散度 Kullback-Leibler divergence： $$ MI(x_i,y)=KL(p(x_i,y)||p(x_i)p(y)) $$ KL散度度量的是 $p(x_i,y)$ 与 $p(x_i)p(y))$ 之间分布的差异程度。如果 $x_i$ 和 $y$ 是独立随机变量，那么 $p(x_i,y)=p(x_i)p(y))$，这时二者的KL散度为零。这和我们的直觉相符，如果 $x_i$ 和 $y$ 相互独立，那么 $x_i$ 对于 $y$ 就没有贡献任何信息量，$S(i)$ 就应当非常小。
最后一个细节：当已经计算好 $S(i)$ 将特征根据重要性进行排序了之后，如何决定使用多少个特征呢？标准的做法是，使用交叉验证来确定 $k$ 值。
正则化是应对过拟合的一个有效方法。之前，在参数拟合的过程中多使用最大似然估计法，根据下面这个公式来选择参数 $$ \theta_{ML}=arg \max_{\theta}\prod_{i=1}^m p(y^{(i)}|x^{(i)};\theta) $$ 在这整个过程中，$\theta$ 都被视作一个确定但未知的常数，这是频率学派 frequentist statistics的视角。在频率学派看来，参数 $\theta$ 并不是随机而仅仅是未知的，我们需要通过某种统计推断（比如最大似然估计法）的手段来估计这个参数。
与此相对，贝叶斯学派 Bayesian statistics将 $\theta$ 看做一个值未知的随机变量。从而，我们可以假设一个关于 $\theta$ 的先验概率 prior distribution $p(\theta)$。而给定训练集 $S=\{(x^{(i)}, y^{(i)})\}_{i=1}^m$，如果这时要对一个新的输入值 $x$ 做预测，我们需要先计算 $\theta$ 的后验概率 posterior distribution $$ \begin{split} p(\theta|S) &= \frac{p(S|\theta)p(\theta)}{p(S)} \\ &= \frac{\prod_{i=1}^m p(y^{(i)}|x^{(i)},\theta)p(\theta)}{\int_{\theta}(\prod_{i=1}^m p(y^{(i)}|x^{(i)},\theta)p(\theta))d\theta} \end{split} $$ 注意到，这时 $\theta$ 已经是一个随机变量，是可以 $p(y^{(i)}|x^{(i)},\theta)$ 的形式作为条件概率的条件出现的（而不是之前的 $p(y^{(i)}|x^{(i)};\theta)$）。
之后，对于新的数据 $x$ 进行预测时，计算其标签的后验概率 $$ p(y|x,S)=\int_{\theta}p(y|x,\theta)p(\theta|S)d\theta $$
因此，如果目标是预测给定 $x$ 时 $y$ 的期望值，那么 $$ E[y|x,S]=\int_{y}yp(y|x,S)dy $$
上面的过程全部都使用了贝叶斯统计学的思路，这样计算开销会无比巨大。因而，在实际中，会使用一些近似的方法来估计 $\theta$ 的后验概率以简化计算。最常见的近似，是使用点估计，最大后验概率估计 maximum a posteriori $$ \theta_{MAP}=arg \max_\theta \prod_{i=1}^m p(y^{(i)}|x^{(i)},\theta)p(\theta) $$ 注意到这个公示仅仅比最大似然估计法在因子中增加了一项 $p(\theta)$。
而实际中，对先验概率 $p(\theta)$ 的假设，通常是 $\theta \sim \mathcal{N}(0,\tau^2I)$。使用这样的先验概率假设，拟合出的参数 $\theta_{MAP}$ 的模会比最大似然估计法小很多。这使得贝叶斯最大后验概率估计更不易受到过拟合的影响。
In [ ]: